Quantum computing utilizes unique quantum features such as quantum coherence and quantum entanglement to solve some problems much faster than on classical Turing machines. In a quantum circuit, information is stored in quantum bits or “qubits.” An important difference between qubits and conventional bits is that rather than being restricted to one of the on and off states, the quantum properties of qubits allow them to maintain a state that is a superposition of both on and off states simultaneously. By exploiting quantum coherence properties between qubits, a collection of n qubits may store 2n bits of information as opposed to the n pieces of information that may be stored by conventional bits.
The most dramatic example of the power of quantum computing is Shor's algorithm to factor a large integer. This algorithm is substantially faster than any known classical algorithm of subexponential complexity. Another major example is the search for an object in unsorted data containing N elements. Classically it would require, on the average, O(N) searches. However, Grover showed that, by employing quantum superposition and quantum entanglement, the search can be carried out with only O(√{square root over (N)}) steps. Grover's algorithm thus represents a polynomial advantage over classical counterparts.
In recent years, Grover's algorithm has been realized in nuclear magnetic resonance, and optical systems, and a proposal has been made for its implementation in cavity quantum electrodynamic systems. All these studies are, however, restricted to searching N=2 qubits for which only one step is required to recover the target state with unit probability. An extension to higher values of N entails additional complications.